VC-dimension of subsets of the Hamming graph

Abstract: Vapnik-Chervonenkis or VC-dimension has been a useful tool in combinatorics, machine learning, and other areas. Given a graph from a well-studied family, there has been recent activity on size thresholds for a subset of a graph to guarantee bounds on the VC-dimension of the subset. These resemble finite point configuration results, such as the Erdos-Falconer distance problem, both in form as well as in the techniques of proof. Typically, one looks at graphs that are highly pseudorandom, such as the distance graph or the dot product graph, but the Hamming graph is quantifiably less pseudorandom, and standard techniques seem to break down and yield very weak results if any. We present a suite of results that outperform their counterparts for the Hamming graph. The proofs are completely elementary, and in some cases, tight.

Mathematics

Audience: researchers in the topic

Combinatorial and additive number theory (CANT 2025)